package leetcode_1100;

/**
 *@author 周杨 
 *PartitionArrayForMaximumSum_1043 给一个数组和k 可以将一个数组分成若干连续子数组 连续子数组的长度不大于k 并且元素可以等于子数组里最大的元素 问如何划分能使数组的元素和最大
 *describe:用动态规划 跟k天买股票是一个题目 AC 100%
 *2019年5月13日 上午13:47
 */
public class PartitionArrayForMaximumSum_1043 {
	public static void main(String[] args) {
		PartitionArrayForMaximumSum_1043 test = new PartitionArrayForMaximumSum_1043();
		System.out.println(test.maxSumAfterPartitioning(new int[] {1,15,7,9,2,5,10}, 3));
	}
	public int maxSumAfterPartitioning(int[] A, int K) {
		int dp[] = new int[A.length+1];//dp[i][j]表示将第i个元素和前j个元素分在一组的最优解
		for(int i=0;i<A.length;++i) {
			int max = A[i];
			dp[i+1] = dp[i]+max;
			for(int j=1;i-j >= 0 && j<K;++j) {
				max = Math.max(max, A[i-j]);
				dp[i+1] = Math.max(dp[i+1], dp[i-j]+max*(j+1));
			}
		}
		return dp[A.length];
	}
}
